﻿/*******************************************************************
 *     JameE
 *******************************************************************
  Copyright 2010 Clifford Champion and JameE contributors.
  
  This file is part of JameE.
  
  JameE is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.
  
  JameE is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.
  
  You should have received a copy of the GNU General Public License
  along with JameE.  If not, see <http://www.gnu.org/licenses/>.
 ******************************************************************/
 

$include(
[

])

$class_static(
"JameE.Utils.Array",
{

	/////////////////////
	// CONSTRUCTORS
	/////////////
	_ctor: function () {

	},


	/////////////////////
	// METHODS
	/////////////
	sequentialSearch: function (arr, fValueOrFnComparer) {
		/// <summary>Searches an array sequentally. If a value is
		/// provided, it is compared using triple-equals operator.
		/// If a function is provided, the function must return 0
		/// if a match occurs. Returns -1 if no match is found.</summary>
		$require_type(arr, "array");

		if (arr.length === 0) {
			return -1;
		}


		var bUseComparer = false;
		if ($typeof(fValueOrFnComparer) === "function") {
			bUseComparer = true;
		}
		else if ($typeof(fValueOrFnComparer) !== "number") {
			throw new Error("Expected number value or comparer.");
		}

		var iLength = arr.length;
		if (bUseComparer) {
			for (var i = 0; i < iLength; ++i) {
				if (fValueOrFnComparer(arr[i]) === 0) {
					return i;
				}
			}
		}
		else {
			for (var i = 0; i < iLength; ++i) {
				if (fValueOrFnComparer === arr[i]) {
					return i;
				}
			}
		}
		return -1;
	},

	binarySearch: function (arr, fValueOrFnComparer) {
		/// <summary>Uses a mid-point hopping search. 
		/// Returns the index of the found entry or -1 if not found.
		/// Assumes array is sorted. If a value is provided, it is compared
		/// using equality and less/greater than operators. If a 
		/// function is provided, the function should return 
		/// -1 to direct the search to lesser values,
		/// +1 to direct the search to greater values,
		/// and 0 in the case of a match.
		/// </summary>
		$require_type(arr, "array");

		if (arr.length === 0) {
			return -1;
		}

		var bUseComparer = false;
		if ($typeof(fValueOrFnComparer) === "function") {
			bUseComparer = true;
		}
		else if ($typeof(fValueOrFnComparer) !== "number") {
			throw new Error("Expected number value or comparer.");
		}


		var iUpperBound = arr.length; // exclusive upper bound
		var iLowerBound = 0; // inclusive lower bound

		if (bUseComparer) {
			while (iLowerBound < iUpperBound) {
				var iTest = Math.floor((iUpperBound + iLowerBound) / 2);

				var oTestValue = arr[iTest];

				var iResult = fValueOrFnComparer(oTestValue);

				if (iResult === 0) {
					return iTest;
				}
				else if (iResult < 0) {
					iUpperBound = iTest;
				}
				else {
					iLowerBound = iTest + 1;
				}
			}
		}
		else {
			while (iLowerBound < iUpperBound) {
				var iTest = Math.floor((iUpperBound + iLowerBound) / 2);

				var oTestValue = arr[iTest];

				if (oTestValue === fValue) {
					return iTest;
				}
				else if (oTestValue < fValue) {
					iUpperBound = iTest;
				}
				else {
					iLowerBound = iTest + 1;
				}
			}
		}
		return -1;
	},

	removeElement: function (arr, oValue) {
		/// <summary>Removes the first matching 
		/// element from the given array.</summary>

		$require_type(arr, "array");
		var iLength = arr.length;
		for (var i = 0; i < iLength; ++i) {
			if (arr[i] === oValue) {
				arr.splice(i, 1);
				return;
			}
		}
	}

});


$include_notify("Utils/Array.js");
